class Solution {
public:
    bool dfs(vector<vector<int>>& graph,int i,int color,vector<int>& res){
        if(res[i]!=-1)
        return res[i]==color;
        res[i]=color;
        for(int j:graph[i]){
            if(!dfs(graph,j,!color,res))
            return false;
        }
        return true;
    }
    bool isBipartite(vector<vector<int>>& graph) {
        int n=graph.size();
        vector<int>res(n,-1);
        for(int i=0;i<n;i++){
            if(res[i]==-1&&!dfs(graph,i,0,res))
            return false;
        }
        return true;
    }
};
